package com.fanshuai.algorithms.backtrack;

/**
 * 二维搜索问题 floodFill算法
 */
public class TwoDementionSearch {

    /**
     * 图片填充颜色
     * 有一个二维数组表示的图像，每个数组元祖表示颜色，在0-65536之间。给定坐标点(x,y)和新的颜色，将所有
     * 符合条件的像素点渲染成新的颜色。符合条件是指：假设(x,y)原先的颜色为oldColor，如果一个像素点向下左右像素点均为oldColor，
     * 则颜色改成newColor
     * @param image
     * @param x
     * @param y
     * @param newColor
     */
    public static void fillImage(int[][] image, int x, int y, int newColor) {
        int width = image.length, height = image[0].length;
        boolean[][] visited = new boolean[width][height];
        fillImage(image, x, y, image[x][y], newColor, visited);
    }

    private static void fillImage(int[][] image, int x, int y, int color, int newColor, boolean[][] visited) {
        int width = image.length, height = image[0].length;
        if (x < 0 || x >= width || y < 0 || y >= height) {
            return;
        }
        if (image[x][y] != color) {
            return;
        }
        if (visited[x][y]) {
            return;
        }

        image[x][y] = newColor;
        visited[x][y] = true;
        fillImage(image, x + 1, y, color, newColor, visited);
        fillImage(image, x - 1, y, color, newColor, visited);
        fillImage(image, x, y + 1, color, newColor, visited);
        fillImage(image, x, y - 1, color, newColor, visited);
    }

    /**
     * 图像魔棒工具
     * 有一个二维数组表示的图像，每个数组元祖表示颜色，在0-65536之间。给定坐标点(x,y)和新的颜色，标记与新的颜色相同的区域边界
     * @param image
     * @param x
     * @param y
     */
    public static void fillEdge(int[][] image, int x, int y, int newColor) {
        boolean[][] visited = new boolean[image.length][image[0].length];
        fillEdge(image, x, y, image[x][y], newColor, visited);
    }

    private static int fillEdge(int[][] image, int x, int y, int color, int newColor, boolean[][] visited) {
        if (x < 0 || x >= image.length || y < 0 || y > image[0].length) {
            return 0;
        }
        if (image[x][y] != color) {
            return 0;
        }
        if (visited[x][y]) {
            return 1;
        }

        visited[x][y] = true;
        int aroundColor =
                fillEdge(image, x + 1, y, color, newColor, visited) +
                fillEdge(image, x - 1, y, color, newColor, visited) +
                fillEdge(image, x, y + 1, color, newColor, visited) +
                fillEdge(image, x, y - 1, color, newColor, visited);
        if (aroundColor < 4) {
            image[x][y] = newColor;
        }

        return 1;
    }

    /**
     * 计算扫雷问题
     * 有一个矩阵，表示扫雷游戏窗口，其中元素值为-1表示此元素是地雷，非地雷的元素，表示该元素周围的地雷总数量。
     * 元素周围共8个方向，为上、下、左、右、左上、左下、右上、右下。
     * 游戏开始时，在随机若干坐标点有地雷，元素值为-1，其他位置未翻开，元素值为-2。
     * 给定一个坐标，需要从该坐标点开始，翻开连通的非地雷区域, 并显示区域内每个元素的地雷数
     * 连通区域指，坐标点的上、下、左、右四个方向之一不是地雷，且已经被翻开。
     * @param bomb
     * @param x
     * @param y
     */
    public static void calcBomb(int[][] bomb, int x, int y) {
        boolean[][] visited = new boolean[bomb.length][bomb[0].length];
        calcBomb(bomb, x, y, visited);
    }

    private static int calcBomb(int[][] bomb, int x, int y, boolean[][] visited) {
        if (x < 0 || x >= bomb.length || y < 0 || y >= bomb[0].length) { //边界
            return 0;
        }
        if (bomb[x][y] == -1) { //地雷
            visited[x][y] = true;
            return 1;
        }
        if (visited[x][y]) {
            return 0;
        }

        visited[x][y] = true;
        int around = calcBomb(bomb, x + 1, y, visited) +
                calcBomb(bomb, x - 1, y, visited) +
                calcBomb(bomb, x, y + 1, visited) +
                calcBomb(bomb, x, y - 1, visited);

        if (inArea(bomb, x - 1, y - 1)) {
            around += bomb[x - 1][y - 1] == -1 ? 1 : 0;
        }
        if (inArea(bomb, x + 1, y - 1)) {
            around += bomb[x + 1][y - 1] == -1 ? 1 : 0;
        }
        if (inArea(bomb, x - 1, y + 1)) {
            around += bomb[x - 1][y + 1] == -1 ? 1 : 0;
        }
        if (inArea(bomb, x + 1, y + 1)) {
            around += bomb[x + 1][y + 1] == -1 ? 1 : 0;
        }
        bomb[x][y] = around;
        return 0;
    }

    private static boolean inArea(int[][] bombs, int x, int y) {
        return x >= 0 && x < bombs.length && y >= 0 && y < bombs[0].length;
    }
}
